#include<iostream>
#include<cassert>
#include<ctime>
#include<cstdlib>
#include<algorithm>
//compare-five-sort-algorithms
using namespace std;
double calc_elapsed_seconds(const struct timespec *ts_from,
        const struct timespec *ts_to)
{
    struct timespec ts_curr;
    time_t ds;
    long dns;

    if (ts_to == NULL) {
        clock_gettime(CLOCK_THREAD_CPUTIME_ID, &ts_curr);
        ts_to = &ts_curr;
    }

    ds = ts_to->tv_sec - ts_from->tv_sec;
    dns = ts_to->tv_nsec - ts_from->tv_nsec;
    return ds + dns * 1.0E-9;
}


size_t partition(int t[], int low, int high) {
    int pivot = t[low];
    while (low < high) {
        while (low < high && t[high] > pivot)
            --high;
        t[low] = t[high];
        while (low < high && t[low] <= pivot)
            ++low;
        t[high] = t[low];
    }
    t[low] = pivot;
    return low;
}

int* quick_sort_(int t[], int low, int high) {
    if (low < high) {
        int pos_pivot = partition(t, low, high);
        quick_sort_(t, low, pos_pivot - 1);
        quick_sort_(t, pos_pivot + 1, high);
    }
    return t;
}

int* quick_sort(int t[], size_t len) {
    if (len == 0) return t;
    return quick_sort_(t, 0, (int)(len - 1));
}


void merge(const int src_a[], size_t len_a, const int src_b[], size_t len_b, int dst[])
{
    size_t i = 0, j = 0, k = 0;
    while (i < len_a && j < len_b) {
        if (src_b[j] < src_a[i]) {
            dst[k] = src_b[j];
            ++j;
        }
        else {
            dst[k] = src_a[i];
            ++i;
        }
        ++k;
    }
    for (; i < len_a; ++i, ++k)
        dst[k] = src_a[i];
    for (; j < len_b; ++j, ++k)
        dst[k] = src_b[j];
}
int* merge_sort_ (int t[], size_t start, size_t stop) {
    if (stop - start <= 1)
        return t;
    size_t mid = start + ((stop - start) >> 1);
    merge_sort_(t, start, mid);
    merge_sort_(t, mid, stop);
    int tmp[stop - start];
    merge(t + start, mid - start, t + mid, stop - mid, tmp);
    for (size_t i = start; i < stop; ++i)
        t[i] = tmp[i - start];
    return t;
}
int* merge_sort (int t[], size_t len) {
	return merge_sort_(t, 0, len - 1);
}


int* insertion_sort (int t[], size_t len) {
    for (size_t i = 1; i < len; i++) {
        int key = t[i];
        ssize_t j = i - 1;
        while (j >= 0 and key < t[j]) {
            t[j + 1] = t[j];
            j--;
        }
        t[j + 1] = key;
    }
    return t;
}


size_t minimum_index(int t[], size_t len)
{
    assert(len > 0);

    size_t min = 0;
    for (size_t i = 1; i < len; i++) {
        if (t[i] < t[min])
            min = i;
    }

    return min;
}
int* selection_sort (int t[], size_t len) {
	size_t start = 0;
    while (true) {
        if (start + 1 == len)
            break;
        size_t min = minimum_index(t + start, len - start);
        min += start;
        if (min != start) {
            swap(t[start], t[min]);
        }

        start++;
    }
    return t;
}


int* bubble_sort (int t[], size_t len) {
	size_t i, j;
    for (i = 0; i < len - 1; i++) {
        for (j = 0; j < len - 1 - i; j++) {
            if (t[j] > t[j + 1])
                swap(t[j], t[j + 1]);
        }
    }
    return t;
}


void print_pointer(int* p, size_t len){
	for (size_t i = 0; i < len; i++) {
        cout << *p << " ";
        p++;
    }
    cout<<endl;
}
int main(){
	int r;
	cin>>r;
	int t[r];
	srandom(time(NULL));
    for (size_t i = 0; i < r; i++) {
        size_t a = static_cast<size_t>(random());
        a %= 10000;
        t[i]=a;
    }
	struct timespec t1;
    clock_gettime(CLOCK_THREAD_CPUTIME_ID, &t1);
    for(int i=0;i<=1000000;++i)
        selection_sort(t,r);
    double duration1 = calc_elapsed_seconds(&t1, NULL);
//struct timespec t1;
//    clock_gettime(CLOCK_THREAD_CPUTIME_ID, &t1);
//    for(int i=0;i<=100000;++i)
//        f1();
//    double duration1 = calc_elapsed_seconds(&t1, NULL);
    
    struct timespec t2;
    clock_gettime(CLOCK_THREAD_CPUTIME_ID, &t2);
    for(int i=0;i<=1000000;++i)
        bubble_sort(t,r);
    double duration2 = calc_elapsed_seconds(&t2, NULL);
    
    struct timespec t3;
    clock_gettime(CLOCK_THREAD_CPUTIME_ID, &t3);
    for(int i=0;i<=1000000;++i)
        insertion_sort(t,r);
    double duration3 = calc_elapsed_seconds(&t3, NULL);
    
    struct timespec t4;
    clock_gettime(CLOCK_THREAD_CPUTIME_ID, &t4);
    for(int i=0;i<=1000000;++i)
        merge_sort(t,r);
    double duration4 = calc_elapsed_seconds(&t4, NULL);
    
    struct timespec t5;
    clock_gettime(CLOCK_THREAD_CPUTIME_ID, &t5);
    for(int i=0;i<=1000000;++i)
        quick_sort(t,r);
    double duration5 = calc_elapsed_seconds(&t5, NULL);
    
    std::cout << "<selection_sort>It took me " << duration1 << " seconds." << std::endl;
    std::cout << "<bubble_sort>It took me " << duration2 << " seconds." << std::endl;
    std::cout << "<insertion_sort>It took me " << duration3 << " seconds." << std::endl;
    std::cout << "<merge_sort>It took me " << duration4 << " seconds." << std::endl;
    std::cout << "<quick_sort>It took me " << duration5 << " seconds." << std::endl;
}
